{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "PGx6PWwhOvf8"
   },
   "source": [
    "# Assignment #2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "aHR_1k1zO1O0"
   },
   "source": [
    "*** Edit this cell ***\n",
    "\n",
    "Enter your details here:\n",
    "\n",
    "**Name #1:** Yishuai Jiang\n",
    "\n",
    "**McGill Id #1:** 260954315\n",
    "\n",
    "\n",
    "**Name #2:** Yue Xu\n",
    "\n",
    "**McGill Id #2:** 260954353\n",
    " \n",
    "ALso save your file as '277_A1_[your mcgill id#1]_[your mcgill id#2]'.\n",
    "\n",
    "Example if your mcgill id is '123456' & '654321', your file should be named as :\n",
    "'277_A1_123456_654321.pynb'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Eq32iJSJsvP0"
   },
   "source": [
    "## Instructions for Assignment 2\n",
    "\n",
    "1. All the submissions should be attempted in a team of 2 students.\n",
    "\n",
    "2. Please submit the assignment on mycources. In case of any issues, you can submit the assignment (jupyter notebook) to arbaaz.khan@mail.mcgill.ca\n",
    "\n",
    "3. Please follow the McGill Integrity code, through out the process of the notebook. Read for more info: Academic Integrity\n",
    "\n",
    "4. A student should be able to replicate the results in the presence of a TA or the Instructor, if asked. If you code is dependent on hyperparameters values, then include appropriate seeding.\n",
    "\n",
    "5. You can add text/code cells as per your need.\n",
    "\n",
    "6. Additional marks for clean and well commented code.\n",
    "\n",
    "7. Please explain any assumption made during the exercise.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "njEE0k4HOlrA"
   },
   "source": [
    "## 1. Monte Carlo Tree Search\n",
    "\n",
    "Points: [50 %]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ZYW1uIteGlG7"
   },
   "outputs": [],
   "source": [
    "#remove \" > /dev/null 2>&1\" to see what is going on under the hood\n",
    "!pip install gym pyvirtualdisplay > /dev/null 2>&1\n",
    "!apt-get install -y xvfb python-opengl ffmpeg > /dev/null 2>&1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "7JJ5cmVrGp4c"
   },
   "outputs": [],
   "source": [
    "import gym\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 151
    },
    "colab_type": "code",
    "id": "3cQLQrLIGqV0",
    "outputId": "be530f3f-88b6-4cc6-a51a-3f84b30517cb"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+---------+\n",
      "|\u001b[34;1mR\u001b[0m: | : :G|\n",
      "| : | : : |\n",
      "| : : : : |\n",
      "| | :\u001b[43m \u001b[0m| : |\n",
      "|\u001b[35mY\u001b[0m| : |B: |\n",
      "+---------+\n",
      "\n"
     ]
    }
   ],
   "source": [
    "env = gym.make('Taxi-v3')\n",
    "env.reset()\n",
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "w4F7eMq-1zrH"
   },
   "source": [
    "**Description of the game:**\n",
    "\n",
    "The aim is to teach a taxi-agent to pick up and drop off passengers at the right locations. There are 4 locations where the taxi can either pick/drop off a passeneger.\n",
    "\n",
    "```\n",
    "(R, G, Y, B)\n",
    "```\n",
    "\n",
    "The solid line-divider (|) is the symbol for a solid seperator which the taxi cannot cross. However, the colon (:) can be crossed over.\n",
    "\n",
    "The game has 2 elements to maximize the reward:\n",
    "\n",
    "```\n",
    "  1. Drop off the passenger at the correct location (either R, G, Y, B).\n",
    "  2. Save passenger's time by taking the shortest route.\n",
    "  3. Take care of passenger's safety by not breaking any traffic rules.\n",
    "```\n",
    "Reward system:\n",
    "```\n",
    "  1. Successful pick up/drop off: +20\n",
    "  2. illegal pickup/drop off: -10 \n",
    "  3. Each step (except the above 2 states): -1\n",
    "```\n",
    "\n",
    "Taking a step() has the following syntax:\n",
    "\n",
    "```\n",
    "next_state, reward, done, info = env.step (action)\n",
    "```\n",
    "\n",
    "The map is $5 \\times 5$ grid. The environment has 500 total possible states. It will be a good practice to calculate this number on your own.\n",
    "\n",
    "Possible actions:\n",
    "\n",
    "      0: South\n",
    "      1: North\n",
    "      2: East\n",
    "      3: West\n",
    "      4: Pickup\n",
    "      5: Drop-off\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 269
    },
    "colab_type": "code",
    "id": "UyemrmdNbYnV",
    "outputId": "2b22dc5d-8ade-413a-ad95-639badc3bf9c"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "248\n",
      "+---------+\n",
      "|\u001b[35mR\u001b[0m: | : :G|\n",
      "| : | : : |\n",
      "| : :\u001b[43m \u001b[0m: : |\n",
      "| | : | : |\n",
      "|\u001b[34;1mY\u001b[0m| : |B: |\n",
      "+---------+\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{0: [(1.0, 348, -1, False)],\n",
       " 1: [(1.0, 148, -1, False)],\n",
       " 2: [(1.0, 268, -1, False)],\n",
       " 3: [(1.0, 228, -1, False)],\n",
       " 4: [(1.0, 248, -10, False)],\n",
       " 5: [(1.0, 248, -10, False)]}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Some helper functions\n",
    "\n",
    "state = env.reset()\n",
    "print(state)\n",
    "env.render()\n",
    "\n",
    "env.P[state]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "31GCUfmfdZ_c"
   },
   "source": [
    "```\n",
    "env.P[state] \n",
    "```\n",
    "returns a dictionary with \n",
    "```\n",
    "keys: all posssible actions, \n",
    "values: (probability, next_state, reward, done)\n",
    "```\n",
    "\n",
    "where\n",
    "\n",
    "```\n",
    "action : ranges from 0 to 5\n",
    "probability: always one (can you think why)\n",
    "next_state: <explained above>\n",
    "reward: <explained above>\n",
    "done: if True, means the episode is over\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 202
    },
    "colab_type": "code",
    "id": "kvzIMzNrGykk",
    "outputId": "128a3e06-3496-47ff-9fc3-b6cf5eeb0bd1"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+---------+\n",
      "|\u001b[35mR\u001b[0m: | : :G|\n",
      "| : |\u001b[43m \u001b[0m: : |\n",
      "| : : : : |\n",
      "| | : | : |\n",
      "|\u001b[34;1mY\u001b[0m| : |B: |\n",
      "+---------+\n",
      "  (North)\n",
      "reward:  -1\n",
      "done:  False\n",
      "NS:  148\n"
     ]
    }
   ],
   "source": [
    "next_state, reward, done, _ = env.step(1) # taxi drops off illegally\n",
    "env.render()\n",
    "print('reward: ', reward)\n",
    "print('done: ', done)\n",
    "print('NS: ', next_state)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Exxnms9z4LQs"
   },
   "source": [
    "I will encourage you to play the game yourself, to gain familiarity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "D_WQAonEkDxy"
   },
   "source": [
    "## 1.1 Implement a MCTS algorithm using UCB"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ZxnkXK8dgexW"
   },
   "outputs": [],
   "source": [
    "# importing modules\n",
    "\n",
    "import os\n",
    "import sys\n",
    "import random\n",
    "from time import time\n",
    "from math import sqrt, log\n",
    "from copy import copy, deepcopy\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "HUlinODCJ7bY"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\t Eps: 1, score:    -7.000,   avg_time: 1.0 s\n",
      "\t Eps: 2, score:     1.000,   avg_time: 1.1 s\n",
      "\t Eps: 3, score:    -8.000,   avg_time: 1.6 s\n",
      "\t Eps: 4, score:   -25.500,   avg_time: 1.6 s\n",
      "\t Eps: 5, score:   -27.000,   avg_time: 1.9 s\n",
      "\t Eps: 6, score:   -28.167,   avg_time: 2.1 s\n",
      "\t Eps: 7, score:   -27.000,   avg_time: 2.1 s\n",
      "\t Eps: 8, score:   -22.375,   avg_time: 2.0 s\n",
      "\t Eps: 9, score:   -21.000,   avg_time: 1.9 s\n",
      "\t Eps: 10, score:   -17.500,   avg_time: 1.9 s\n",
      "\t Eps: 11, score:   -15.636,   avg_time: 2.0 s\n",
      "\t Eps: 12, score:   -15.583,   avg_time: 2.2 s\n",
      "\t Eps: 13, score:   -19.385,   avg_time: 2.2 s\n",
      "\t Eps: 14, score:   -19.571,   avg_time: 2.1 s\n",
      "\t Eps: 15, score:   -22.267,   avg_time: 2.2 s\n",
      "\t Eps: 16, score:   -21.688,   avg_time: 2.1 s\n",
      "\t Eps: 17, score:   -19.941,   avg_time: 2.0 s\n",
      "\t Eps: 18, score:   -18.056,   avg_time: 2.0 s\n",
      "\t Eps: 19, score:   -20.947,   avg_time: 2.1 s\n",
      "\t Eps: 20, score:   -19.600,   avg_time: 2.0 s\n",
      "\t Eps: 21, score:   -18.524,   avg_time: 2.0 s\n",
      "\t Eps: 22, score:   -19.955,   avg_time: 2.0 s\n",
      "\t Eps: 23, score:   -21.130,   avg_time: 2.1 s\n",
      "\t Eps: 24, score:   -20.625,   avg_time: 2.1 s\n",
      "\t Eps: 25, score:   -19.880,   avg_time: 2.1 s\n",
      "\t Eps: 26, score:   -19.269,   avg_time: 2.1 s\n",
      "\t Eps: 27, score:   -18.407,   avg_time: 2.1 s\n",
      "\t Eps: 28, score:   -18.214,   avg_time: 2.1 s\n",
      "\t Eps: 29, score:   -17.207,   avg_time: 2.0 s\n",
      "\t Eps: 30, score:   -16.067,   avg_time: 2.0 s\n",
      "\t Eps: 31, score:   -15.323,   avg_time: 1.9 s\n",
      "\t Eps: 32, score:   -16.156,   avg_time: 1.9 s\n",
      "\t Eps: 33, score:   -16.152,   avg_time: 1.9 s\n",
      "\t Eps: 34, score:   -15.471,   avg_time: 1.9 s\n",
      "\t Eps: 35, score:   -15.057,   avg_time: 1.9 s\n",
      "\t Eps: 36, score:   -14.139,   avg_time: 1.8 s\n",
      "\t Eps: 37, score:   -15.000,   avg_time: 1.9 s\n",
      "\t Eps: 38, score:   -14.132,   avg_time: 1.9 s\n",
      "\t Eps: 39, score:   -13.564,   avg_time: 1.9 s\n",
      "\t Eps: 40, score:   -14.775,   avg_time: 1.9 s\n",
      "\t Eps: 41, score:   -14.171,   avg_time: 1.9 s\n",
      "\t Eps: 42, score:   -13.738,   avg_time: 1.9 s\n",
      "\t Eps: 43, score:   -13.023,   avg_time: 1.9 s\n",
      "\t Eps: 44, score:   -12.295,   avg_time: 1.9 s\n",
      "\t Eps: 45, score:   -12.511,   avg_time: 2.0 s\n",
      "\t Eps: 46, score:   -12.870,   avg_time: 2.0 s\n",
      "\t Eps: 47, score:   -12.255,   avg_time: 1.9 s\n",
      "\t Eps: 48, score:   -11.688,   avg_time: 1.9 s\n",
      "\t Eps: 49, score:   -11.837,   avg_time: 1.9 s\n",
      "\t Eps: 50, score:   -11.820,   avg_time: 1.9 s\n",
      "\t Eps: 51, score:   -12.020,   avg_time: 1.9 s\n",
      "\t Eps: 52, score:   -12.481,   avg_time: 1.9 s\n",
      "\t Eps: 53, score:   -12.264,   avg_time: 1.9 s\n",
      "\t Eps: 54, score:   -12.278,   avg_time: 1.9 s\n",
      "\t Eps: 55, score:   -12.509,   avg_time: 2.0 s\n",
      "\t Eps: 56, score:   -12.143,   avg_time: 1.9 s\n",
      "\t Eps: 57, score:   -12.088,   avg_time: 2.0 s\n",
      "\t Eps: 58, score:   -11.586,   avg_time: 1.9 s\n",
      "\t Eps: 59, score:   -11.441,   avg_time: 1.9 s\n",
      "\t Eps: 60, score:   -11.467,   avg_time: 1.9 s\n",
      "\t Eps: 61, score:   -11.754,   avg_time: 1.9 s\n",
      "\t Eps: 62, score:   -12.129,   avg_time: 1.9 s\n",
      "\t Eps: 63, score:   -11.730,   avg_time: 1.9 s\n",
      "\t Eps: 64, score:   -12.125,   avg_time: 1.9 s\n",
      "\t Eps: 65, score:   -12.138,   avg_time: 2.0 s\n",
      "\t Eps: 66, score:   -12.167,   avg_time: 1.9 s\n",
      "\t Eps: 67, score:   -11.940,   avg_time: 1.9 s\n",
      "\t Eps: 68, score:   -12.500,   avg_time: 2.0 s\n",
      "\t Eps: 69, score:   -12.899,   avg_time: 2.0 s\n",
      "\t Eps: 70, score:   -12.629,   avg_time: 1.9 s\n",
      "\t Eps: 71, score:   -12.704,   avg_time: 2.0 s\n",
      "\t Eps: 72, score:   -12.333,   avg_time: 2.0 s\n",
      "\t Eps: 73, score:   -12.260,   avg_time: 1.9 s\n",
      "\t Eps: 74, score:   -12.257,   avg_time: 1.9 s\n",
      "\t Eps: 75, score:   -12.573,   avg_time: 2.0 s\n",
      "\t Eps: 76, score:   -12.434,   avg_time: 1.9 s\n",
      "\t Eps: 77, score:   -12.662,   avg_time: 1.9 s\n",
      "\t Eps: 78, score:   -12.256,   avg_time: 1.9 s\n",
      "\t Eps: 79, score:   -12.266,   avg_time: 1.9 s\n",
      "\t Eps: 80, score:   -11.925,   avg_time: 1.9 s\n",
      "\t Eps: 81, score:   -12.469,   avg_time: 1.9 s\n",
      "\t Eps: 82, score:   -12.585,   avg_time: 1.9 s\n",
      "\t Eps: 83, score:   -12.229,   avg_time: 1.9 s\n",
      "\t Eps: 84, score:   -12.000,   avg_time: 1.9 s\n",
      "\t Eps: 85, score:   -11.729,   avg_time: 1.9 s\n",
      "\t Eps: 86, score:   -11.407,   avg_time: 1.9 s\n",
      "\t Eps: 87, score:   -11.529,   avg_time: 1.9 s\n",
      "\t Eps: 88, score:   -11.511,   avg_time: 1.9 s\n",
      "\t Eps: 89, score:   -11.258,   avg_time: 1.9 s\n",
      "\t Eps: 90, score:   -10.956,   avg_time: 1.9 s\n",
      "\t Eps: 91, score:   -11.791,   avg_time: 1.9 s\n",
      "\t Eps: 92, score:   -11.717,   avg_time: 1.9 s\n",
      "\t Eps: 93, score:   -11.398,   avg_time: 1.9 s\n",
      "\t Eps: 94, score:   -11.511,   avg_time: 1.9 s\n",
      "\t Eps: 95, score:   -12.105,   avg_time: 1.9 s\n",
      "\t Eps: 96, score:   -11.792,   avg_time: 1.9 s\n",
      "\t Eps: 97, score:   -12.052,   avg_time: 1.9 s\n",
      "\t Eps: 98, score:   -12.010,   avg_time: 1.9 s\n",
      "\t Eps: 99, score:   -12.020,   avg_time: 1.9 s\n",
      "\t Eps: 100, score:   -12.230,   avg_time: 1.9 s\n",
      "\t Eps: 101, score:   -12.230,   avg_time: 1.9 s\n",
      "\t Eps: 102, score:   -12.230,   avg_time: 1.9 s\n",
      "\t Eps: 103, score:   -12.230,   avg_time: 1.9 s\n",
      "\t Eps: 104, score:   -11.770,   avg_time: 1.9 s\n",
      "\t Eps: 105, score:   -11.530,   avg_time: 1.9 s\n",
      "\t Eps: 106, score:   -11.030,   avg_time: 1.8 s\n",
      "\t Eps: 107, score:   -10.970,   avg_time: 1.9 s\n",
      "\t Eps: 108, score:   -10.970,   avg_time: 1.9 s\n",
      "\t Eps: 109, score:   -10.970,   avg_time: 1.8 s\n",
      "\t Eps: 110, score:   -10.970,   avg_time: 1.8 s\n",
      "\t Eps: 111, score:   -10.970,   avg_time: 1.8 s\n",
      "\t Eps: 112, score:   -10.970,   avg_time: 1.9 s\n",
      "\t Eps: 113, score:   -10.970,   avg_time: 1.9 s\n",
      "\t Eps: 114, score:   -10.970,   avg_time: 1.9 s\n",
      "\t Eps: 115, score:   -10.970,   avg_time: 1.9 s\n",
      "\t Eps: 116, score:   -10.970,   avg_time: 1.9 s\n",
      "\t Eps: 117, score:   -10.970,   avg_time: 1.9 s\n",
      "\t Eps: 118, score:   -10.970,   avg_time: 1.9 s\n",
      "\t Eps: 119, score:   -10.970,   avg_time: 1.9 s\n",
      "\t Eps: 120, score:   -10.970,   avg_time: 1.9 s\n",
      "\t Eps: 121, score:   -10.970,   avg_time: 2.0 s\n",
      "\t Eps: 122, score:   -10.970,   avg_time: 2.0 s\n",
      "\t Eps: 123, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 124, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 125, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 126, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 127, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 128, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 129, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 130, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 131, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 132, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 133, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 134, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 135, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 136, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 137, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 138, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 139, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 140, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 141, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 142, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 143, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 144, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 145, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 146, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 147, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 148, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 149, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 150, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 151, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 152, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 153, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 154, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 155, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 156, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 157, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 158, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 159, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 160, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 161, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 162, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 163, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 164, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 165, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 166, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 167, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 168, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 169, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 170, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 171, score:   -10.830,   avg_time: 2.0 s\n",
      "\t Eps: 172, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 173, score:   -10.830,   avg_time: 1.9 s\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\t Eps: 174, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 175, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 176, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 177, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 178, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 179, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 180, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 181, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 182, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 183, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 184, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 185, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 186, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 187, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 188, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 189, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 190, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 191, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 192, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 193, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 194, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 195, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 196, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 197, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 198, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 199, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 200, score:   -10.830,   avg_time: 1.9 s\n",
      "\t Eps: 201, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 202, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 203, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 204, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 205, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 206, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 207, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 208, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 209, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 210, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 211, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 212, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 213, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 214, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 215, score:   -10.450,   avg_time: 2.0 s\n",
      "\t Eps: 216, score:   -10.450,   avg_time: 2.0 s\n",
      "\t Eps: 217, score:   -10.450,   avg_time: 2.0 s\n",
      "\t Eps: 218, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 219, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 220, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 221, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 222, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 223, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 224, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 225, score:   -10.450,   avg_time: 1.9 s\n",
      "\t Eps: 226, score:   -10.100,   avg_time: 1.9 s\n",
      "\t Eps: 227, score:   -10.020,   avg_time: 1.9 s\n",
      "\t Eps: 228, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 229, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 230, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 231, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 232, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 233, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 234, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 235, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 236, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 237, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 238, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 239, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 240, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 241, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 242, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 243, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 244, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 245, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 246, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 247, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 248, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 249, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 250, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 251, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 252, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 253, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 254, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 255, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 256, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 257, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 258, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 259, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 260, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 261, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 262, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 263, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 264, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 265, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 266, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 267, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 268, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 269, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 270, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 271, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 272, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 273, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 274, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 275, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 276, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 277, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 278, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 279, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 280, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 281, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 282, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 283, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 284, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 285, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 286, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 287, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 288, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 289, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 290, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 291, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 292, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 293, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 294, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 295, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 296, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 297, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 298, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 299, score:    -9.780,   avg_time: 1.9 s\n",
      "\t Eps: 300, score:    -9.780,   avg_time: 1.9 s\n"
     ]
    }
   ],
   "source": [
    "def moving_average(v, n):\n",
    "    n = min(len(v), n)\n",
    "    ret = [.0]*(len(v)-n+1)\n",
    "    ret[0] = float(sum(v[:n]))/n\n",
    "    for i in range(len(v)-n):\n",
    "        ret[i+1] = ret[i] + float(v[n+i] - v[i])/n\n",
    "    return ret\n",
    "\n",
    "def ucb(node):\n",
    "## TO-DO ##\n",
    "    return node.value / node.visits + sqrt(log(node.parent.visits)/node.visits)\n",
    "\n",
    "def combinations(space):\n",
    "    if isinstance(space, gym.spaces.Discrete):\n",
    "        return range(space.n)\n",
    "    elif isinstance(space, gym.spaces.Tuple):\n",
    "        return itertools.product(*[combinations(s) for s in space.spaces])\n",
    "    else:\n",
    "        raise NotImplementedError\n",
    "## End TO-DO ##\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, parent, action):\n",
    "        self.parent = parent\n",
    "        self.action = action\n",
    "        self.children = []\n",
    "        self.explored_children = 0\n",
    "        self.visits = 0\n",
    "        self.value = 0\n",
    "\n",
    "class Taxi_agent:\n",
    "    def __init__(self, env_name, max_eps=300, max_depth=1000, max_steps=10000):#改回300\n",
    "        self.env_name = 'Taxi-v3'\n",
    "        \n",
    "        self.max_eps = max_eps\n",
    "        self.max_depth = max_depth\n",
    "        self.max_steps = max_steps\n",
    "\n",
    "    def print_stats(self, episode, score, avg_time):\n",
    "        print('\\t Eps: {}, score:{:10.3f},   avg_time:{:4.1f} s'.format(episode, score, avg_time))\n",
    "\n",
    "    def run(self):\n",
    "        best_rewards = []\n",
    "        start_time = time()\n",
    "        env = gym.make(self.env_name)\n",
    "\n",
    "        for episode in range(self.max_eps):\n",
    "            env.reset()\n",
    "            root = Node(None, None)\n",
    "\n",
    "            best_actions = []\n",
    "            best_reward = float(\"-inf\")\n",
    "\n",
    "            for _ in range(self.max_steps):\n",
    "                \n",
    "                sum_reward = 0\n",
    "                node = root\n",
    "                terminal = False\n",
    "                actions = []\n",
    "\n",
    "# selection\n",
    "                ## To - DO ##\n",
    "                state = copy(env)\n",
    "                while node.children:\n",
    "#                     print(\"select@@@@@@@@@@@@@@@@\")\n",
    "                    if node.explored_children < len(node.children):\n",
    "#                         print(\"value,visits\",node.value,node.visits)\n",
    "                        child = node.children[node.explored_children]\n",
    "                        node.explored_children += 1\n",
    "                        node = child\n",
    "                    else:\n",
    "                        node = max(node.children, key=ucb)\n",
    "#                         print(\"ucb:\",ucb(node))\n",
    "                    _, reward, terminal, _ = state.step(node.action)\n",
    "                    sum_reward += reward\n",
    "                    actions.append(node.action)\n",
    "                ## End To-DO ##\n",
    "\n",
    "# expansion\n",
    "                ## To - DO ##\n",
    "                # 新建子节点\n",
    "                if not terminal:\n",
    "#                     print(\"expansion\")\n",
    "                    node.children = [Node(node, a) for a in combinations(state.action_space)]\n",
    "                    random.shuffle(node.children)\n",
    "                ## End To-DO ##\n",
    "\n",
    "# simulation\n",
    "                \n",
    "                ## To - DO ##\n",
    "                # 找到终点\n",
    "#                 print(\"simulation\")\n",
    "                while not terminal:    \n",
    "                    action = state.action_space.sample()\n",
    "                    next_state, reward, terminal, _ = state.step(action)\n",
    "                    \n",
    "                    sum_reward += reward\n",
    "                    actions.append(action)\n",
    "\n",
    "                    if len(actions) > self.max_depth:\n",
    "                        sum_reward -= 100\n",
    "                        break\n",
    "                ## End To-DO ##\n",
    "                \n",
    "                # remember best\n",
    "                if best_reward < sum_reward:\n",
    "                    best_reward = sum_reward\n",
    "                    best_actions = actions\n",
    "\n",
    "# backpropagate\n",
    "                ## To - DO ##\n",
    "                while node:\n",
    "#                     print(\"backpropagate\")\n",
    "                    node.visits += 1\n",
    "                    node.value += sum_reward\n",
    "                    node = node.parent\n",
    "                ## End To-DO ##\n",
    "\n",
    "            sum_reward = 0\n",
    "            for action in best_actions:\n",
    "                _, reward, terminal, _ = env.step(action)\n",
    "                sum_reward += reward\n",
    "                if terminal:\n",
    "                    break\n",
    "\n",
    "            best_rewards.append(sum_reward)\n",
    "            score = max(moving_average(best_rewards, 100))\n",
    "            avg_time = (time()-start_time)/(episode+1)\n",
    "            self.print_stats(episode+1, score, avg_time)\n",
    "\n",
    "\n",
    "def main():\n",
    "\n",
    "    # Taxi-Agent\n",
    "    Taxi_agent('Taxi-v3',   max_eps=300, max_steps=4000, max_depth=50).run()\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "imOlh7R_jrh-"
   },
   "source": [
    "## 1.2 Reimplement the above code with MCTS with $\\epsilon$ - greedy  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "lNWG5ytPibJA"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\t Eps: 1, score:   -33.000,   avg_time: 2.8 s\n",
      "\t Eps: 2, score:   -38.500,   avg_time: 2.8 s\n",
      "\t Eps: 3, score:   -40.667,   avg_time: 2.8 s\n",
      "\t Eps: 4, score:   -46.500,   avg_time: 2.8 s\n",
      "\t Eps: 5, score:   -45.400,   avg_time: 2.8 s\n",
      "\t Eps: 6, score:   -43.167,   avg_time: 2.7 s\n",
      "\t Eps: 7, score:   -43.000,   avg_time: 2.7 s\n",
      "\t Eps: 8, score:   -41.750,   avg_time: 2.6 s\n",
      "\t Eps: 9, score:   -41.667,   avg_time: 2.6 s\n",
      "\t Eps: 10, score:   -41.600,   avg_time: 2.6 s\n",
      "\t Eps: 11, score:   -43.818,   avg_time: 2.6 s\n",
      "\t Eps: 12, score:   -43.667,   avg_time: 2.6 s\n",
      "\t Eps: 13, score:   -43.462,   avg_time: 2.6 s\n",
      "\t Eps: 14, score:   -43.214,   avg_time: 2.6 s\n",
      "\t Eps: 15, score:   -43.067,   avg_time: 2.6 s\n",
      "\t Eps: 16, score:   -43.000,   avg_time: 2.6 s\n",
      "\t Eps: 17, score:   -43.588,   avg_time: 2.6 s\n",
      "\t Eps: 18, score:   -44.056,   avg_time: 2.6 s\n",
      "\t Eps: 19, score:   -44.000,   avg_time: 2.6 s\n",
      "\t Eps: 20, score:   -44.950,   avg_time: 2.6 s\n",
      "\t Eps: 21, score:   -44.429,   avg_time: 2.6 s\n",
      "\t Eps: 22, score:   -43.000,   avg_time: 2.6 s\n",
      "\t Eps: 23, score:   -42.870,   avg_time: 2.6 s\n",
      "\t Eps: 24, score:   -42.917,   avg_time: 2.6 s\n",
      "\t Eps: 25, score:   -43.240,   avg_time: 2.6 s\n",
      "\t Eps: 26, score:   -43.192,   avg_time: 2.6 s\n",
      "\t Eps: 27, score:   -43.407,   avg_time: 2.6 s\n",
      "\t Eps: 28, score:   -42.607,   avg_time: 2.6 s\n",
      "\t Eps: 29, score:   -43.034,   avg_time: 2.6 s\n",
      "\t Eps: 30, score:   -42.333,   avg_time: 2.6 s\n",
      "\t Eps: 31, score:   -42.323,   avg_time: 2.6 s\n",
      "\t Eps: 32, score:   -40.906,   avg_time: 2.6 s\n",
      "\t Eps: 33, score:   -40.939,   avg_time: 2.6 s\n",
      "\t Eps: 34, score:   -42.118,   avg_time: 2.6 s\n",
      "\t Eps: 35, score:   -40.371,   avg_time: 2.6 s\n",
      "\t Eps: 36, score:   -39.667,   avg_time: 2.6 s\n",
      "\t Eps: 37, score:   -40.622,   avg_time: 2.6 s\n",
      "\t Eps: 38, score:   -40.737,   avg_time: 2.6 s\n",
      "\t Eps: 39, score:   -40.513,   avg_time: 2.6 s\n",
      "\t Eps: 40, score:   -40.525,   avg_time: 2.6 s\n",
      "\t Eps: 41, score:   -40.537,   avg_time: 2.6 s\n",
      "\t Eps: 42, score:   -40.571,   avg_time: 2.6 s\n",
      "\t Eps: 43, score:   -39.186,   avg_time: 2.6 s\n",
      "\t Eps: 44, score:   -37.864,   avg_time: 2.6 s\n",
      "\t Eps: 45, score:   -38.067,   avg_time: 2.6 s\n",
      "\t Eps: 46, score:   -37.587,   avg_time: 2.6 s\n",
      "\t Eps: 47, score:   -36.745,   avg_time: 2.6 s\n",
      "\t Eps: 48, score:   -36.854,   avg_time: 2.6 s\n",
      "\t Eps: 49, score:   -37.184,   avg_time: 2.6 s\n",
      "\t Eps: 50, score:   -37.460,   avg_time: 2.6 s\n",
      "\t Eps: 51, score:   -37.549,   avg_time: 2.6 s\n",
      "\t Eps: 52, score:   -37.654,   avg_time: 2.6 s\n",
      "\t Eps: 53, score:   -37.717,   avg_time: 2.6 s\n",
      "\t Eps: 54, score:   -37.630,   avg_time: 2.6 s\n",
      "\t Eps: 55, score:   -37.764,   avg_time: 2.6 s\n",
      "\t Eps: 56, score:   -38.518,   avg_time: 2.6 s\n",
      "\t Eps: 57, score:   -38.632,   avg_time: 2.6 s\n",
      "\t Eps: 58, score:   -38.690,   avg_time: 2.6 s\n",
      "\t Eps: 59, score:   -38.610,   avg_time: 2.6 s\n",
      "\t Eps: 60, score:   -38.333,   avg_time: 2.6 s\n",
      "\t Eps: 61, score:   -38.377,   avg_time: 2.6 s\n",
      "\t Eps: 62, score:   -38.435,   avg_time: 2.6 s\n",
      "\t Eps: 63, score:   -38.794,   avg_time: 2.6 s\n",
      "\t Eps: 64, score:   -38.875,   avg_time: 2.6 s\n",
      "\t Eps: 65, score:   -39.015,   avg_time: 2.6 s\n",
      "\t Eps: 66, score:   -38.288,   avg_time: 2.6 s\n",
      "\t Eps: 67, score:   -38.328,   avg_time: 2.6 s\n",
      "\t Eps: 68, score:   -38.500,   avg_time: 2.6 s\n",
      "\t Eps: 69, score:   -37.681,   avg_time: 2.6 s\n",
      "\t Eps: 70, score:   -37.457,   avg_time: 2.6 s\n",
      "\t Eps: 71, score:   -36.676,   avg_time: 2.6 s\n",
      "\t Eps: 72, score:   -36.750,   avg_time: 2.6 s\n",
      "\t Eps: 73, score:   -36.822,   avg_time: 2.6 s\n",
      "\t Eps: 74, score:   -36.878,   avg_time: 2.6 s\n",
      "\t Eps: 75, score:   -36.933,   avg_time: 2.6 s\n",
      "\t Eps: 76, score:   -36.987,   avg_time: 2.6 s\n",
      "\t Eps: 77, score:   -36.688,   avg_time: 2.6 s\n",
      "\t Eps: 78, score:   -36.205,   avg_time: 2.6 s\n",
      "\t Eps: 79, score:   -36.316,   avg_time: 2.5 s\n",
      "\t Eps: 80, score:   -36.275,   avg_time: 2.5 s\n",
      "\t Eps: 81, score:   -36.395,   avg_time: 2.5 s\n",
      "\t Eps: 82, score:   -36.110,   avg_time: 2.5 s\n",
      "\t Eps: 83, score:   -36.241,   avg_time: 2.5 s\n",
      "\t Eps: 84, score:   -36.190,   avg_time: 2.5 s\n",
      "\t Eps: 85, score:   -35.541,   avg_time: 2.5 s\n",
      "\t Eps: 86, score:   -35.488,   avg_time: 2.5 s\n",
      "\t Eps: 87, score:   -35.609,   avg_time: 2.5 s\n",
      "\t Eps: 88, score:   -35.398,   avg_time: 2.5 s\n",
      "\t Eps: 89, score:   -35.034,   avg_time: 2.5 s\n",
      "\t Eps: 90, score:   -34.989,   avg_time: 2.5 s\n",
      "\t Eps: 91, score:   -34.626,   avg_time: 2.5 s\n",
      "\t Eps: 92, score:   -34.163,   avg_time: 2.5 s\n",
      "\t Eps: 93, score:   -34.366,   avg_time: 2.5 s\n",
      "\t Eps: 94, score:   -34.170,   avg_time: 2.5 s\n",
      "\t Eps: 95, score:   -34.263,   avg_time: 2.5 s\n",
      "\t Eps: 96, score:   -34.365,   avg_time: 2.5 s\n",
      "\t Eps: 97, score:   -34.227,   avg_time: 2.5 s\n",
      "\t Eps: 98, score:   -34.602,   avg_time: 2.5 s\n",
      "\t Eps: 99, score:   -34.566,   avg_time: 2.5 s\n",
      "\t Eps: 100, score:   -34.130,   avg_time: 2.5 s\n",
      "\t Eps: 101, score:   -33.610,   avg_time: 2.5 s\n",
      "\t Eps: 102, score:   -33.580,   avg_time: 2.5 s\n",
      "\t Eps: 103, score:   -33.370,   avg_time: 2.5 s\n",
      "\t Eps: 104, score:   -33.330,   avg_time: 2.5 s\n",
      "\t Eps: 105, score:   -33.330,   avg_time: 2.5 s\n",
      "\t Eps: 106, score:   -33.330,   avg_time: 2.5 s\n",
      "\t Eps: 107, score:   -33.330,   avg_time: 2.5 s\n",
      "\t Eps: 108, score:   -33.330,   avg_time: 2.5 s\n",
      "\t Eps: 109, score:   -33.190,   avg_time: 2.5 s\n",
      "\t Eps: 110, score:   -33.130,   avg_time: 2.5 s\n",
      "\t Eps: 111, score:   -32.780,   avg_time: 2.5 s\n",
      "\t Eps: 112, score:   -32.690,   avg_time: 2.5 s\n",
      "\t Eps: 113, score:   -32.690,   avg_time: 2.5 s\n",
      "\t Eps: 114, score:   -32.690,   avg_time: 2.5 s\n",
      "\t Eps: 115, score:   -32.690,   avg_time: 2.5 s\n",
      "\t Eps: 116, score:   -32.690,   avg_time: 2.5 s\n",
      "\t Eps: 117, score:   -32.670,   avg_time: 2.5 s\n",
      "\t Eps: 118, score:   -32.480,   avg_time: 2.5 s\n",
      "\t Eps: 119, score:   -31.990,   avg_time: 2.5 s\n",
      "\t Eps: 120, score:   -31.770,   avg_time: 2.5 s\n",
      "\t Eps: 121, score:   -31.770,   avg_time: 2.5 s\n",
      "\t Eps: 122, score:   -31.770,   avg_time: 2.5 s\n",
      "\t Eps: 123, score:   -31.770,   avg_time: 2.5 s\n",
      "\t Eps: 124, score:   -31.770,   avg_time: 2.5 s\n",
      "\t Eps: 125, score:   -31.770,   avg_time: 2.5 s\n",
      "\t Eps: 126, score:   -31.770,   avg_time: 2.5 s\n",
      "\t Eps: 127, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 128, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 129, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 130, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 131, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 132, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 133, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 134, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 135, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 136, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 137, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 138, score:   -31.740,   avg_time: 2.6 s\n",
      "\t Eps: 139, score:   -31.740,   avg_time: 2.6 s\n",
      "\t Eps: 140, score:   -31.740,   avg_time: 2.6 s\n",
      "\t Eps: 141, score:   -31.740,   avg_time: 2.6 s\n",
      "\t Eps: 142, score:   -31.740,   avg_time: 2.6 s\n",
      "\t Eps: 143, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 144, score:   -31.740,   avg_time: 2.6 s\n",
      "\t Eps: 145, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 146, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 147, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 148, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 149, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 150, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 151, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 152, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 153, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 154, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 155, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 156, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 157, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 158, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 159, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 160, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 161, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 162, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 163, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 164, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 165, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 166, score:   -31.740,   avg_time: 2.5 s\n",
      "\t Eps: 167, score:   -31.730,   avg_time: 2.5 s\n",
      "\t Eps: 168, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 169, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 170, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 171, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 172, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 173, score:   -31.040,   avg_time: 2.5 s\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\t Eps: 174, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 175, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 176, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 177, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 178, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 179, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 180, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 181, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 182, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 183, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 184, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 185, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 186, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 187, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 188, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 189, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 190, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 191, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 192, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 193, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 194, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 195, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 196, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 197, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 198, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 199, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 200, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 201, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 202, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 203, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 204, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 205, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 206, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 207, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 208, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 209, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 210, score:   -31.040,   avg_time: 2.5 s\n",
      "\t Eps: 211, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 212, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 213, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 214, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 215, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 216, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 217, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 218, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 219, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 220, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 221, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 222, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 223, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 224, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 225, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 226, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 227, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 228, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 229, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 230, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 231, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 232, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 233, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 234, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 235, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 236, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 237, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 238, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 239, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 240, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 241, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 242, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 243, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 244, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 245, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 246, score:   -31.040,   avg_time: 2.6 s\n",
      "\t Eps: 247, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 248, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 249, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 250, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 251, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 252, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 253, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 254, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 255, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 256, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 257, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 258, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 259, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 260, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 261, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 262, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 263, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 264, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 265, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 266, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 267, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 268, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 269, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 270, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 271, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 272, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 273, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 274, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 275, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 276, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 277, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 278, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 279, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 280, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 281, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 282, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 283, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 284, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 285, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 286, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 287, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 288, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 289, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 290, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 291, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 292, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 293, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 294, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 295, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 296, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 297, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 298, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 299, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 300, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 301, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 302, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 303, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 304, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 305, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 306, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 307, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 308, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 309, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 310, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 311, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 312, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 313, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 314, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 315, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 316, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 317, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 318, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 319, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 320, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 321, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 322, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 323, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 324, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 325, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 326, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 327, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 328, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 329, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 330, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 331, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 332, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 333, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 334, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 335, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 336, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 337, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 338, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 339, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 340, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 341, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 342, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 343, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 344, score:   -31.040,   avg_time: 2.7 s\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\t Eps: 345, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 346, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 347, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 348, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 349, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 350, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 351, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 352, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 353, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 354, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 355, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 356, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 357, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 358, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 359, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 360, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 361, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 362, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 363, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 364, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 365, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 366, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 367, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 368, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 369, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 370, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 371, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 372, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 373, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 374, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 375, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 376, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 377, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 378, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 379, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 380, score:   -31.040,   avg_time: 2.7 s\n",
      "\t Eps: 381, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 382, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 383, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 384, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 385, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 386, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 387, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 388, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 389, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 390, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 391, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 392, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 393, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 394, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 395, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 396, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 397, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 398, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 399, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 400, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 401, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 402, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 403, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 404, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 405, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 406, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 407, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 408, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 409, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 410, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 411, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 412, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 413, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 414, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 415, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 416, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 417, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 418, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 419, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 420, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 421, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 422, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 423, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 424, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 425, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 426, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 427, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 428, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 429, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 430, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 431, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 432, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 433, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 434, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 435, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 436, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 437, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 438, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 439, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 440, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 441, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 442, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 443, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 444, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 445, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 446, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 447, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 448, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 449, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 450, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 451, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 452, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 453, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 454, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 455, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 456, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 457, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 458, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 459, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 460, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 461, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 462, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 463, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 464, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 465, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 466, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 467, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 468, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 469, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 470, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 471, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 472, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 473, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 474, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 475, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 476, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 477, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 478, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 479, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 480, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 481, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 482, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 483, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 484, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 485, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 486, score:   -31.040,   avg_time: 2.8 s\n",
      "\t Eps: 487, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 488, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 489, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 490, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 491, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 492, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 493, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 494, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 495, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 496, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 497, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 498, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 499, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 500, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 501, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 502, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 503, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 504, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 505, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 506, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 507, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 508, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 509, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 510, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 511, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 512, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 513, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 514, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 515, score:   -31.040,   avg_time: 2.9 s\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\t Eps: 516, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 517, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 518, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 519, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 520, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 521, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 522, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 523, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 524, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 525, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 526, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 527, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 528, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 529, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 530, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 531, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 532, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 533, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 534, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 535, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 536, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 537, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 538, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 539, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 540, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 541, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 542, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 543, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 544, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 545, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 546, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 547, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 548, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 549, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 550, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 551, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 552, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 553, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 554, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 555, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 556, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 557, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 558, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 559, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 560, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 561, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 562, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 563, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 564, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 565, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 566, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 567, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 568, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 569, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 570, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 571, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 572, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 573, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 574, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 575, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 576, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 577, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 578, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 579, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 580, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 581, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 582, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 583, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 584, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 585, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 586, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 587, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 588, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 589, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 590, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 591, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 592, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 593, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 594, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 595, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 596, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 597, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 598, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 599, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 600, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 601, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 602, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 603, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 604, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 605, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 606, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 607, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 608, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 609, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 610, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 611, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 612, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 613, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 614, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 615, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 616, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 617, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 618, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 619, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 620, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 621, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 622, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 623, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 624, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 625, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 626, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 627, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 628, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 629, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 630, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 631, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 632, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 633, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 634, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 635, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 636, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 637, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 638, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 639, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 640, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 641, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 642, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 643, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 644, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 645, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 646, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 647, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 648, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 649, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 650, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 651, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 652, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 653, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 654, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 655, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 656, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 657, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 658, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 659, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 660, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 661, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 662, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 663, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 664, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 665, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 666, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 667, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 668, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 669, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 670, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 671, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 672, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 673, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 674, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 675, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 676, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 677, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 678, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 679, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 680, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 681, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 682, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 683, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 684, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 685, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 686, score:   -31.040,   avg_time: 2.9 s\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\t Eps: 687, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 688, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 689, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 690, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 691, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 692, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 693, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 694, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 695, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 696, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 697, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 698, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 699, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 700, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 701, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 702, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 703, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 704, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 705, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 706, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 707, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 708, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 709, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 710, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 711, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 712, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 713, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 714, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 715, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 716, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 717, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 718, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 719, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 720, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 721, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 722, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 723, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 724, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 725, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 726, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 727, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 728, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 729, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 730, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 731, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 732, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 733, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 734, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 735, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 736, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 737, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 738, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 739, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 740, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 741, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 742, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 743, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 744, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 745, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 746, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 747, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 748, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 749, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 750, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 751, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 752, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 753, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 754, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 755, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 756, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 757, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 758, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 759, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 760, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 761, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 762, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 763, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 764, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 765, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 766, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 767, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 768, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 769, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 770, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 771, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 772, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 773, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 774, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 775, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 776, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 777, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 778, score:   -31.040,   avg_time: 2.9 s\n",
      "\t Eps: 779, score:   -31.030,   avg_time: 2.9 s\n",
      "\t Eps: 780, score:   -30.910,   avg_time: 2.9 s\n",
      "\t Eps: 781, score:   -30.910,   avg_time: 2.9 s\n",
      "\t Eps: 782, score:   -30.490,   avg_time: 2.9 s\n",
      "\t Eps: 783, score:   -30.490,   avg_time: 2.9 s\n",
      "\t Eps: 784, score:   -30.490,   avg_time: 2.9 s\n",
      "\t Eps: 785, score:   -30.490,   avg_time: 2.9 s\n",
      "\t Eps: 786, score:   -30.490,   avg_time: 2.9 s\n",
      "\t Eps: 787, score:   -30.490,   avg_time: 2.9 s\n",
      "\t Eps: 788, score:   -30.490,   avg_time: 2.9 s\n",
      "\t Eps: 789, score:   -30.490,   avg_time: 2.9 s\n",
      "\t Eps: 790, score:   -30.490,   avg_time: 2.9 s\n",
      "\t Eps: 791, score:   -30.250,   avg_time: 2.9 s\n",
      "\t Eps: 792, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 793, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 794, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 795, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 796, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 797, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 798, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 799, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 800, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 801, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 802, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 803, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 804, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 805, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 806, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 807, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 808, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 809, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 810, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 811, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 812, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 813, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 814, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 815, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 816, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 817, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 818, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 819, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 820, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 821, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 822, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 823, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 824, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 825, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 826, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 827, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 828, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 829, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 830, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 831, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 832, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 833, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 834, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 835, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 836, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 837, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 838, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 839, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 840, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 841, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 842, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 843, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 844, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 845, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 846, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 847, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 848, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 849, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 850, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 851, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 852, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 853, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 854, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 855, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 856, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 857, score:   -30.220,   avg_time: 2.9 s\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\t Eps: 858, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 859, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 860, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 861, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 862, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 863, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 864, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 865, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 866, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 867, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 868, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 869, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 870, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 871, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 872, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 873, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 874, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 875, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 876, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 877, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 878, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 879, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 880, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 881, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 882, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 883, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 884, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 885, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 886, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 887, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 888, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 889, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 890, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 891, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 892, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 893, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 894, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 895, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 896, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 897, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 898, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 899, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 900, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 901, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 902, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 903, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 904, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 905, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 906, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 907, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 908, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 909, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 910, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 911, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 912, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 913, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 914, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 915, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 916, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 917, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 918, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 919, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 920, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 921, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 922, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 923, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 924, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 925, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 926, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 927, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 928, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 929, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 930, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 931, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 932, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 933, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 934, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 935, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 936, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 937, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 938, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 939, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 940, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 941, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 942, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 943, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 944, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 945, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 946, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 947, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 948, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 949, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 950, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 951, score:   -30.220,   avg_time: 2.8 s\n",
      "\t Eps: 952, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 953, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 954, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 955, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 956, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 957, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 958, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 959, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 960, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 961, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 962, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 963, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 964, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 965, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 966, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 967, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 968, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 969, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 970, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 971, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 972, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 973, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 974, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 975, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 976, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 977, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 978, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 979, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 980, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 981, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 982, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 983, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 984, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 985, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 986, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 987, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 988, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 989, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 990, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 991, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 992, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 993, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 994, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 995, score:   -30.220,   avg_time: 2.9 s\n",
      "\t Eps: 996, score:   -30.220,   avg_time: 2.9 s\n"
     ]
    }
   ],
   "source": [
    "\n",
    "def moving_average(v, n):\n",
    "    n = min(len(v), n)\n",
    "    ret = [.0]*(len(v)-n+1)\n",
    "    ret[0] = float(sum(v[:n]))/n\n",
    "    for i in range(len(v)-n):\n",
    "        ret[i+1] = ret[i] + float(v[n+i] - v[i])/n\n",
    "    return ret\n",
    "\n",
    "def epsilon_greedy(node):\n",
    "    ## To-DO\n",
    "    max_value = -100\n",
    "    ind_max = 0\n",
    "    for i in range(len(node.children)):\n",
    "        if node.children[i].value >max_value:\n",
    "            max_value = node.children[i].value\n",
    "            ind_max = i\n",
    "    e = 0.618\n",
    "    r = random.random()\n",
    "    if r > e:\n",
    "        return node.children[ind_max]\n",
    "    else:\n",
    "        return node.children[random.randint(0,len(node.children)-1)]\n",
    "    ## End To-DO\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, parent, action):\n",
    "        self.parent = parent\n",
    "        self.action = action\n",
    "        self.children = []\n",
    "        self.explored_children = 0\n",
    "        self.visits = 0\n",
    "        self.value = 0\n",
    "\n",
    "class Taxi_agent:\n",
    "    def __init__(self, env_name, max_eps=300, max_depth=1000, max_steps=10000):\n",
    "        self.env_name = 'Taxi-v3'\n",
    "        \n",
    "        self.max_eps = max_eps\n",
    "        self.max_depth = max_depth\n",
    "        self.max_steps = max_steps\n",
    "\n",
    "    def print_stats(self, episode, score, avg_time):\n",
    "        print('\\t Eps: {}, score:{:10.3f},   avg_time:{:4.1f} s'.format(episode, score, avg_time))\n",
    "\n",
    "    def run(self):\n",
    "        best_rewards = []\n",
    "        start_time = time()\n",
    "        env = gym.make(self.env_name)\n",
    "\n",
    "        for episode in range(self.max_eps):\n",
    "            env.reset()\n",
    "            root = Node(None, None)\n",
    "\n",
    "            best_actions = []\n",
    "            best_reward = float(\"-inf\")\n",
    "            \n",
    "            # 每一次的策略\n",
    "            for _ in range(self.max_steps):\n",
    "\n",
    "                sum_reward = 0\n",
    "                node = root\n",
    "                terminal = False\n",
    "                actions = []\n",
    "# 从根节点 R 开始，递归选择最优的子节点（后面会解释）直到达到叶子节点 L。\n",
    "# selection\n",
    "                ## To - DO ##\n",
    "                state = copy(env)\n",
    "                while node.children:\n",
    "                    child = epsilon_greedy(node)    \n",
    "                    node = child\n",
    "                    _, reward, terminal, _ = state.step(node.action)\n",
    "                    sum_reward += reward\n",
    "                    actions.append(node.action)\n",
    "                ## End To-DO ##\n",
    "\n",
    "# expansion\n",
    "                ## To - DO ##\n",
    "                if not terminal:\n",
    "                    node.children = [Node(node, a) for a in combinations(state.action_space)]\n",
    "                    random.shuffle(node.children)\n",
    "                ## End To-DO ##\n",
    "\n",
    "# simulation\n",
    "                \n",
    "                ## To - DO ##\n",
    "                while not terminal:\n",
    "                    action = state.action_space.sample()\n",
    "                    _, reward, terminal, _ = state.step(action)\n",
    "                    sum_reward += reward\n",
    "                    actions.append(action)\n",
    "\n",
    "                    if len(actions) > self.max_depth:\n",
    "                        sum_reward -= 100\n",
    "                        break\n",
    "                ## End To-DO ##\n",
    "\n",
    "                # remember best\n",
    "                if best_reward < sum_reward:\n",
    "                    best_reward = sum_reward\n",
    "                    best_actions = actions\n",
    "\n",
    "# backpropagate\n",
    "                ## To - DO ##\n",
    "                while node:\n",
    "                    node.visits += 1\n",
    "                    node.value += sum_reward\n",
    "                    node = node.parent\n",
    "                ## End To-DO ##\n",
    "                # 每一次策略到此 结束\n",
    "                \n",
    "            sum_reward = 0\n",
    "            for action in best_actions:\n",
    "                _, reward, terminal, _ = env.step(action)\n",
    "                sum_reward += reward\n",
    "                if terminal:\n",
    "                    break\n",
    "\n",
    "            best_rewards.append(sum_reward)\n",
    "            score = max(moving_average(best_rewards, 100))\n",
    "            avg_time = (time()-start_time)/(episode+1)\n",
    "            self.print_stats(episode+1, score, avg_time)\n",
    "# 每一轮到此结束\n",
    "\n",
    "def main():\n",
    "\n",
    "    # Taxi-Agent\n",
    "    Taxi_agent('Taxi-v3',   max_eps=1000, max_steps=4000, max_depth=50).run()\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "knwhwXcUkd1i"
   },
   "source": [
    "# Q2 Hidden Markov Model (HMM)\n",
    "\n",
    "Check the pdf "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# p_s = 0.8p_s + 0.4p_c\n",
    "# p_c = 0.2p_s + 0.6p_c\n",
    "# p_c + p_s = 1\n",
    "# SO: p_c = 1/3   p_s = 2/3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# moods = ['H', 'G', 'H'] \n",
    "# p(s/h) = p(s)*p(h/s)/p(h) = p(s)*p(h/s)/(p(s)*p(h/s)+p(c)*p(h/c))\n",
    "# when happy probability of sunny is\n",
    "2/3*0.8/(2/3*0.8+1/3*0.4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# p(s/g)\n",
    "2/3 * 0.2/(2/3*0.2+1/3*0.4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "wVZv-jG5kovE"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0.8, 0.2), (0.49350649350649356, 0.5064935064935066), (0.728097299525871, 0.27190270047412907)]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['S', 'C', 'S']"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from numpy import random\n",
    "# Transition Probabilities\n",
    "p_ss = 0.8\n",
    "p_sc = 0.2\n",
    "p_cs = 0.4\n",
    "p_cc = 0.6\n",
    "\n",
    "# Initial Probabilities\n",
    "p_s = 2/3\n",
    "p_c = 1/3\n",
    "\n",
    "# Emission Probabilities\n",
    "p_sh = 0.8\n",
    "p_sg = 0.2\n",
    "p_ch = 0.4\n",
    "p_cg = 0.6\n",
    "\n",
    "moods = ['H', 'G', 'H']\n",
    "probabilities = []\n",
    "weather = []\n",
    "\n",
    "if moods[0] == 'H':\n",
    "    probabilities.append((p_s*p_sh/(p_s*p_sh+p_c*p_ch), p_c*p_ch/(p_c*p_ch+p_s*p_sh)))\n",
    "else:\n",
    "    probabilities.append((p_s*p_sc/(p_s*p_sc+p_c*p_cc), p_c*p_cc/(p_c*p_cc+p_s*p_sc)))\n",
    "\n",
    "for i in range(1,len(moods)):\n",
    "    yesterday_sunny, yesterday_cloudy = probabilities[-1]\n",
    "    if moods[i] == 'H':\n",
    "        today_sunny = yesterday_sunny*p_ss*p_sh/(p_ss*p_sh+p_sc*p_ch)+yesterday_cloudy*p_cs*p_sh/(p_cs*p_sh+p_cc*p_ch)\n",
    "        today_cloudy = yesterday_cloudy*p_cc*p_ch/(p_cc*p_ch+p_cs*p_sh) + yesterday_sunny*p_sc*p_ch/(p_sc*p_ch+p_ss*p_sh)\n",
    "        probabilities.append((today_sunny,today_cloudy))\n",
    "    else:\n",
    "        today_sunny = yesterday_sunny*p_ss*p_sg/(p_ss*p_sg+p_sc*p_cg)+yesterday_cloudy*p_cs*p_sg/(p_cs*p_sg+p_cc*p_cg)\n",
    "        today_cloudy = yesterday_cloudy*p_cc*p_cg/(p_cc*p_cg+p_cs*p_sg) + yesterday_sunny*p_sc*p_cg/(p_sc*p_cg+p_ss*p_sg)\n",
    "        probabilities.append((today_sunny, today_cloudy))\n",
    "print(probabilities)\n",
    "for p in probabilities:\n",
    "    if p[0] > p[1]:\n",
    "        weather.append('S')\n",
    "    else:\n",
    "        weather.append('C')\n",
    "        \n",
    "weather"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "pro = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.2874565961764478, 0.10734859862874709, 0.29502124344424907, 0.11017356175055622, 0.07186414904411195, 0.02683714965718677, 0.07375531086106227, 0.027543390437639054]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1.0000000000000002"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pro = []\n",
    "for i in range(2):\n",
    "    for j in range(2):\n",
    "        for k in range(2):\n",
    "            pro.append(probabilities[0][i]*probabilities[1][j]*probabilities[2][k])\n",
    "print(pro)\n",
    "sum(pro)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.2874565961764478"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# SSS =\n",
    "probabilities[0][0]*probabilities[1][0]*probabilities[2][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.10734859862874709"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# SSC =\n",
    "probabilities[0][0]*probabilities[1][0]*probabilities[2][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.29502124344424907"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# SCS =\n",
    "probabilities[0][0]*probabilities[1][1]*probabilities[2][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.11017356175055622"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# SCC=\n",
    "probabilities[0][0]*probabilities[1][1]*probabilities[2][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.07186414904411195"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# CSS\n",
    "probabilities[0][1]*probabilities[1][0]*probabilities[2][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.02683714965718677"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# CSC\n",
    "probabilities[0][1]*probabilities[1][0]*probabilities[2][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.07375531086106227"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# CCS\n",
    "probabilities[0][1]*probabilities[1][1]*probabilities[2][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.027543390437639054"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# CCC\n",
    "probabilities[0][1]*probabilities[1][1]*probabilities[2][1]"
   ]
  }
 ],
 "metadata": {
  "accelerator": "GPU",
  "colab": {
   "collapsed_sections": [],
   "name": "YCBS_277_A2.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
